|
In mathematics, the Cheeger constant (also Cheeger number or isoperimetric number) of a graph is a numerical measure of whether or not a graph has a "bottleneck". The Cheeger constant as a measure of "bottleneckedness" is of great interest in many areas: for example, constructing well-connected networks of computers, card shuffling. The graph theoretical notion originated after the Cheeger isoperimetric constant of a compact Riemannian manifold. The Cheeger constant is named after the mathematician Jeff Cheeger. ==Definition== Let be an undirected finite graph with vertex set and edge set . For a collection of vertices , let denote the collection of all edges going from a vertex in to a vertex outside of : : (Remember that edges are unordered, so the edge is the same as the edge .) Then the Cheeger constant of , denoted , is defined by : The Cheeger constant is strictly positive if and only if is a connected graph. Intuitively, if the Cheeger constant is small but positive, then there exists a "bottleneck", in the sense that there are two "large" sets of vertices with "few" links (edges) between them. The Cheeger constant is "large" if any possible division of the vertex set into two subsets has "many" links between those two subsets. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Cheeger constant (graph theory)」の詳細全文を読む スポンサード リンク
|